package com.kevin.Code.OfferReviewVersion2;

/**
 * @author Vinlee Xiao
 * @Classname SimilarStringGroups
 * @Description Leetcode 839. 相似字符串组 同剑指Offer II 117 困难题 并查集
 * @Date 2022/1/22 10:45
 * @Version 1.0
 */
public class SimilarStringGroups {

    /**
     * @param strs
     * @return
     */
    public int numSimilarGroups(String[] strs) {
        //用于记录字符组的个数
        int countNum = strs.length;
        int[] parent = new int[strs.length];

        //初始化parent
        for (int i = 0; i < strs.length; i++) {
            parent[i] = i;
        }


        for (int i = 0; i < strs.length; i++) {
            for (int j = i + 1; j < strs.length; j++) {
                //如果两个子集同义异位能够转换，就合并两个子集
                if (isSimilar(strs[i], strs[j]) && isUnion(strs, parent, i, j)) {
                    //合并两个子集后,字符串数组中的字符数组个数就减少了
                    countNum--;
                }
            }
        }
        return countNum;
    }

    /**
     * 合并两个子集
     *
     * @param strs
     * @param i
     * @param j
     * @return
     */
    private boolean isUnion(String[] strs, int[] parent, int i, int j) {

        int subGraph1 = findCommonParent(parent, i);
        int subGraph2 = findCommonParent(parent, j);

        //如果两个子字符串的根节点不相同,合并两个子集
        //细节问题要注意
        if (subGraph1 != subGraph2) {
            parent[subGraph1] = subGraph2;
            return true;
        }
        return false;
    }

    /**
     * 查找共同的祖先节点
     *
     * @param parent
     * @param i
     * @return
     */
    private int findCommonParent(int[] parent, int i) {
        if (parent[i] != i) {
            return findCommonParent(parent, parent[i]);
        }
        return parent[i];
    }


    /**
     * 计算两个字符串 不相同的个数位
     * 如果大于2个 说明不能通过交换两个位置 得到另外一个字符串
     *
     * @param str1
     * @param str2
     * @return
     */
    private boolean isSimilar(String str1, String str2) {
        int countDiffrence = 0;

        for (int i = 0; i < str1.length(); i++) {
            if (str1.charAt(i) != str2.charAt(i)) {
                countDiffrence++;
            }

            if (countDiffrence > 2) {
                return false;
            }
        }
        return countDiffrence <= 2;
    }
}
